package cn.xyfmzmy.timingwheel;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicReference;

/**
 * 并发无锁队列 Multi-Producer Single-Consumer （这里实际上是一个单向的链表）
 * 适合多个生产者，一个消费者, 基于CAS原子变量实现不加锁也能保证线程安全，同时提升处理性能
 * 这里用 MpscTaskQueue 来替换原来的 Slot，实测比加锁快得多
 * Producer: 添加延迟任务的多个线程
 * Consumer: 时间轮的触发线程
 */
public class MpscTaskQueue {

    // 链表的头结点 (这里是单向链表)
    private final AtomicReference<TimerWheel.DelayTask> head = new AtomicReference<>(null);

    // 添加延迟任务，这里用头插法，让生产者在队列的头部进行竞争，确保后续节点的消费不背影响
    public void pushTask(TimerWheel.DelayTask delayTask){
        while (true){
            TimerWheel.DelayTask oldHead = head.get();
            delayTask.next = oldHead;
            // 基于CAS变量保证线程安全，确保当前delayTask被添加到头结点
            if(head.compareAndSet(oldHead,delayTask)){
                return;
            }
        }
    }

    // 移除并返回当前时间应当执行的任务集合
    public List<Runnable> removeAndReturnShouldRun(long tickTime){
        List<Runnable> result = new ArrayList<>();
        TimerWheel.DelayTask current = head.get();
        TimerWheel.DelayTask pre = null;
        while(current != null){
            // 不在当前时间范围内，继续往后遍历
            if(current.deadline > tickTime){
                pre = current;
                current = current.next;
                continue;
            }
            TimerWheel.DelayTask next = current.next;
            // 前驱不为null(非头节点),移除并返回
            if(pre != null){
                pre.next = next;
                result.add(current.runnable);
                current.next = null;
                current = next;
                continue;
            }
            // 当前节点为头结点，且尝试更新头结点成功
            if (head.compareAndSet(current,next)) {
                result.add(current.runnable);
                current.next = null;
                current = next;
                continue;
            }
            // 当前节点为头节点，尝试更新失败，重新再来
            current = head.get();
        }
        return result;
    }
}
